// Copyright (c) 2019 Razeware LLC
// For full license & permission details, see LICENSE.markdown.

public class QNode<T> {
  
  public var value: T
  public var next: QNode<T>?
  public var previous: QNode<T>?
  
  public init(value: T) {
    self.value = value
  }
}

extension QNode: CustomStringConvertible {
  
  public var description: String {
    String(describing: value)
  }
}

public class DoublyLinkedList<T> {
  
  private var head: QNode<T>?
  private var tail: QNode<T>?
  
  public init() { }
  
  public var isEmpty: Bool {
    head == nil
  }
  
  public var first: QNode<T>? {
    head
  }
  
  public func append(_ value: T) {
    let newQNode = QNode(value: value)
    
    guard let tailQNode = tail else {
      head = newQNode
      tail = newQNode
      return
    }
    
    newQNode.previous = tailQNode
    tailQNode.next = newQNode
    tail = newQNode
  }
  
  public func remove(_ QNode: QNode<T>) -> T {
    let prev = QNode.previous
    let next = QNode.next
    
    if let prev = prev {
      prev.next = next
    } else {
      head = next
    }
    
    next?.previous = prev
    
    if next == nil {
      tail = prev
    }
    
    QNode.previous = nil
    QNode.next = nil
    
    return QNode.value
  }
}

extension DoublyLinkedList: CustomStringConvertible {
  
  public var description: String {
    var string = ""
    var current = head
    while let QNode = current {
      string.append("\(QNode.value) -> ")
      current = QNode.next
    }
    return string + "end"
  }
}

public class LinkedListIterator<T>: IteratorProtocol {
  
  private var current: QNode<T>?
  
  init(QNode: QNode<T>?) {
    current = QNode
  }
  
  public func next() -> QNode<T>? {
    defer { current = current?.next }
    return current
  }
}

extension DoublyLinkedList: Sequence {
  
  public func makeIterator() -> LinkedListIterator<T> {
    LinkedListIterator(QNode: head)
  }
}
